This invention relates generally to the early conceptual design of objects using computer-aided design (CAD) systems. More particularly, the invention relates to CAD systems, and methods usable in CAD systems, which allow extremely rapid creation of xe2x80x9croughxe2x80x9d or conceptual geometric models of objects without having to precisely describe the specific dimensions, locations, and other characteristics of their geometric subcomponents. The invention further relates to CAD systems, and methods usable in CAD systems, which allow creation and editing of geometric models in such a manner that the created/edited model is output very rapidly after the designer""s input is provided (i.e., the final model is produced almost instantaneously after input), so as to enhance the ability to interactively create and edit designs.
The ability to design (i.e., create, edit, visualize, and/or manipulate) two- and three-dimensional models of objects is a fundamental activity in diverse fields such as engineering, architecture, etc. From an engineering perspective, this process is especially important during the conceptual design stage of an object when the final geometric details of the object are unknown. See, e.g., D. L. Jenkins, R. R. Martin, xe2x80x9cThe Importance of Free-Hand Sketching in Conceptual Design: Automatic Sketch Input,xe2x80x9d Proc. of the 1993 ASME Design Technical Conference, Albuquerque, N.Mex., Sep. 19-22, 1993, pp. 115-128. Typical solutions include making use of two-dimensional (2D) sketches to visualize concepts under discussion, or using a Computer-Aided Design (CAD) system to create a prototypical geometric model. Regarding 2D sketching, this suffers from the drawback that it does not readily allow editing and manipulation of the model (the model must be redrawn), and additionally visualization of the 2D-modeled object in three dimensions is difficult. As for CAD, it is a very useful tool, but it is complex and frequently requires detailed user input in order to generate a desired geometric model. For example, when generating a geometric model in conventional CAD systems, significant details must be provided to the CAD system, such as the specific shapes, dimensions, and locations of the geometric subcomponents of the model. Clearly, when working on a final model of an object, the need to enter this degree of detail might be expected if the designer is to obtain the desired amount of precision in the completed model. However, in the early stages of design where the parameters of the object being designed are conceptual and indefinite rather than certain, this need for high human/CAD system interaction is stifling and greatly hinders creativity in the design process. This is especially true where the immediate goal of the designer is to merely capture the rough shape of an object in the CAD systemxe2x80x94in essence, to make a rapid xe2x80x9cCAD sketchxe2x80x9d of the object. In this case, while the designer wishes to take a fast, freewheeling approach to setting forth his or her design concepts, the CAD system""s requirements for specificity demand that the designer slow down and provide explicit instructions for all aspects of the object being designed. This informational and time burden increases with the complexity of the CAD system and its human/CAD interface; for example, while modern graphical user interfaces make design of geometric models acceptably rapid in many 2D CAD systems, the ab initio design of objects in 3D CAD systems is still time-consuming and frustrating. The burden grows particularly acute for 3D CAD systems where the human/CAD interface is complexxe2x80x94for example, in Virtual Reality (VR) interfaces wherein the designer works within a Virtual Environment (VE)xe2x80x94owing to the increased processing requirements of such systems.
As a result of the above-noted problems, researchers have attempted to devise methods and apparata which simplify the input process to CAD systems so that a user is not constrained by complex input processes, and is freer to input conceptual designs in a more rapid fashion. As an example, U.S. Pat. No. 5,504,854 to Yamashita illustrates an xe2x80x9cApparatus and Method for Inputting Cell Shape and Position and Inter-Cell Calculation.xe2x80x9d This invention creates a series of meta-functions that allow an operator to specify specific shapes and shading using an input device, such as a keyboard or a mouse. When shapes are to be copied or moved, these meta-functions are invoked, thereby reducing the user""s burden in specifying the details associated with the shapes to be moved.
To U.S. Pat. No. 5,742,291 to Palm was issued for a xe2x80x9cMethod and Apparatus for Creation of Three-Dimensional Wire Frames.xe2x80x9d This invention addresses rapid creation of representations of three dimensional objects using generically-shaped wire frames which belong to classes of objects. These generic wire frames can then be modified to correspond to a specific shape desired by a user. This avoids the user""s need to create individual shapes for subsequent manipulation.
U.S. Pat. No. 5,758,122, to Corda et al. was issued for an xe2x80x9cImmersive Visual Programming System.xe2x80x9d While this invention is directed to the field of software programming/development, it is nevertheless of interest because it allows the user to select from a set of prefabricated virtual components, thus saving the user the time and effort of creating individual components.
U.S. Pat. No.5,177,689 to Kinasi et al. was issued for a xe2x80x9cCAD/CAM Apparatus for Enhancing Operator Entry of Machining Attributes and Geometric Shapes.xe2x80x9d This invention relates to the use of simplified forms of input to create numerical control data for machining shapes so that the designer does not need to learn complicated data entry instructions.
U.S. Pat. No. 5,659,493 was issued to Kindena et al. for a xe2x80x9cVirtual Machining Techniques for Modifying Computer Models of Parts.xe2x80x9d This invention represents three-dimensional objects by a high density data point model. A virtual tool is provided to the user, who manipulates the tool on the surface of the displayed object to modify its shape. Thus, the object can be modified without having to input specific equations or data points associated with the desired modifications.
The above inventions generally use standard man-machine interfaces (e.g., mouse, keyboard, 2D video monitor output) to create designs. However, in more recent years, there has been greater interest in the use of more natural forms of input (such as hand motion input or voice command input), and in Virtual Environments (VE) wherein the user is xe2x80x9cimmersedxe2x80x9d in a 3D design environment, owing to the tremendous potential advantages offered by their use. See, e.g., D. Dietz, xe2x80x9cReal Engineering in a Virtual World,xe2x80x9d Mechanical Engineering Magazine, vol. 117, no.7, July, 1995, pp. 78-85; T. H. Dani and R. Gadh, xe2x80x9cVirtual Reality: A New Tool for the Mechanical Engineer,xe2x80x9d Mechanical Engineers Handbook, Myer Kutz, (Ed.), John Wiley and Sons, 1997. As an example, various research projects conducted by the inventors named in this document have investigated inputting shapes into a computer system in a physically intuitive way, using voice, hand motions, and gestures in fashions similar to the way in which one person would communicate with another. By use of position gloves and the like, a CAD system could allow a user to xe2x80x9cgrabxe2x80x9d a design and manipulate it as if holding it in his or her hand, thus providing a more natural and intuitive interaction with the objects that are being designed. This increases design speed and reduces the need to learn complex operating instructions prior to initiating the design process.
Other prior research has also been performed on xe2x80x9cnaturalxe2x80x9d forms of user input such as voice commands and hand gestures. See, e.g., D. Weimer, S. K. Ganapathy, xe2x80x9cA Synthetic Visual Environment with Hand Gesture and Voice Inputxe2x80x9d, Proceedings of the ACM Conference on Computer Human Interfaces, May 1989, pp. 235-240; R. A. Bolt, xe2x80x9cPut That There: Voice and Gesture at the Graphics Interface,xe2x80x9d Computer Graphics, vol. 14, no. 2, pp. 262, 1980. Herranz et al. have developed an interface that utilize two-handed, glove-based input coupled with voice and gaze information to determine the user""s intent for different tasks (see, e.g., E. Herranz, R. A. Bolt, xe2x80x9cTwo-Handed Gesture In Multi-Modal Natural Dialoguexe2x80x9d, Proceedings of the ACM Symposium on User Interface Software Technology, Nov. 15-18, 1992, pp. 7-14). Another system that focuses mainly on hand gestures for interaction is the PolyShop environment (D. P. Mapes, J. M. Moshell, xe2x80x9cA Two-handed Interface for Object Manipulation in a Virtual Environment,xe2x80x9d Presence, vol. 4, no. 4, Fall 1995, pp. 403-416). It allows usage of both hands for various tasks in a VE. Other research has focused on voice and gesture based systems for selection of entities in a geographical map based on spatial relationships; for example, xe2x80x9cselect the house beside that road,xe2x80x9d etc. (Y. A. Tijerno, K. Mochizuiki, F. Kishino, xe2x80x9cInteractive 3-D Computer Graphics Driven Through Verbal Instructions: Previous and Current Activities at ATR,xe2x80x9d Computer and Graphics, vol. 18, no.5, pp.621-631, 1994.) With the exception of the research reported by Weimer et al., the foregoing systems were not specifically intended for CAD, but are reported here for completeness.
Other research has addressed input devices suitable for use in VE environments. As an example, VE pointers/wands have been developed which allow users to point towards displayed objects to select or otherwise manipulate them. Notable among these are the xe2x80x9cBeamCursorxe2x80x9d (see, e.g., T. Yoshimura, Y. Nakamura, M. Sugiura, xe2x80x9c3D Direct Manipulation Interface: Development of Zashiki-Warashu System,xe2x80x9d Computers and Graphics, vol. 18, no. 2, pp. 201-207, 1992) and the xe2x80x9cLaserGunxe2x80x9d (see, e.g., J. Liang, xe2x80x9cJDCAD: A Highly Interactive 3D Modeling System,xe2x80x9d Computer Graphics, v. 18, no. 4, 1994, pp. 499-506).
Other research has extended beyond modes of user input and has specifically addressed the use of VE in CAD systems. Some researchers have approached the use of VE in CAD systems by creating models using conventional CAD systems and then xe2x80x9cimportingxe2x80x9d the models (after an appropriate translation process) into a VE for display. This approach faces several difficulties:
(1) The model must still be first defined in a CAD system using precise shapes, dimensions, locations, etc. (which, as noted above, are typically not well-defined at the concept stage). Thus, the aforementioned difficulties with specificity of input and time burdens are still present.
(2) During the process of translation, topological relationships between entities in the model may be lost. As a consequence, editing the model requires a return to the CAD environment so that the desired changes can be made, and the model must then be xe2x80x9cre-importedxe2x80x9d into the VE for verification.
Examples of such approaches for visualization are the Interactive Visualizer developed at the Graphics, Visualization and Usability Center of the Georgia Institute of Technology (Atlanta, Ga., USA, WWW URL http://www. cc. gatech. edu/gvu/virtual/index_main. html, and the VENUS prototyping project being developed at CERN, the European Center for Nuclear Research (details available at WWW URL: http://sgvenus. cern. ch/VENUS/vr_project. html).
A more useful application of Virtual Environments (VE) that goes beyond these xe2x80x9cvisualization onlyxe2x80x9d systems is the interactive design of shapes in a VE. Such a system gives the engineer a better design tool that is especially useful during the conceptual design stage. As an example, the aforementioned research by Weimer et al. describes a CAD interface using a VPL DataGlove(trademark) (for capturing hand gestures) and spoken commands (with a vocabulary of about 40 phrases) for creating CAD models. Modeling tools are provided for both free-form shape design and parametric shape design (i.e., design using predefined shape features). The parametric design tools allow object/feature selection and manipulation, an additionally incorporate geometric constraints for object placement. The free-form design tools allow xe2x80x9csculptingxe2x80x9d of surfaces that are represented as uniform b-splines and which can be reshaped by perturbing the control points.
Another system is 3-Draw which allows the design of wire-frame like sketches of 3D free-form curve-based geometry (see, e.g., E. Sachs, A. Roberts, D. Stoops, xe2x80x9c3-Draw: A Tool for Designing 3D Shapes,xe2x80x9d IEEE Computer Graphics and Applications, Vol. 11, no. 11, pp. 18-26, 1991). In this system, the designer uses a pair of 6DOF (six degree-of-freedom) tracking devices (one in each hand). One hand is used to hold the object being sketched, and the other hand holds a stylus which serves as the 3D sketching tool. Curves are represented by first-degree cardinal splines interpolated from points in space obtained via the Polhemus(trademark) tracker. The developers of this system also describe user interaction methods for curve selection, creation and editing. Design tools for curve-shaping included methods based on constrained curve manipulation and methods based on direct manipulation of control points.
While the previous two CAD systems were primarily directed towards creating free-form surface and curve geometry respectively, a system specifically oriented towards the design of engineering components is the aforementioned JDCAD system of Liang (for which a citation was provided earlier). This system aims to provide an intuitive, easy-to-use modeling environment for early stage design. Its researchers describe interaction techniques for navigation, object selection and editing based on 3D menus and icons which are selected via a 6DOF device. The modeling operations are based on creation of primitives via 3D rubber-banding techniques and the use of CSG (Constructive Solid Geometry) operations to create more complex geometry. Region-based reshaping, which involves changing primitive dimensions via xe2x80x9chandlesxe2x80x9d situated thereon, is used for editing. Rotational and translational constraints combined with a 3D snapping feature act as design aids during model creation.
Trika, Banedee and Kashyap (xe2x80x9cVirtual Reality Interfaces for Feature-Based Computer-Aided Design Systemsxe2x80x9d, Computer-Aided Design, vol. 29, no. 8, 1997, pp. 565-574) investigated use of a wand interface (a three dimensional mouse) and a speech input system to simplify the input of design features. This research addressed the issue of the complexity of feature-based and constraint-based design within CAD systems. Feature-based design starts with simple shapes which are then modified by attaching features, such as holes, slots, etc. to modify the simple shapes into the one desired. Constraint-based design involves specifying existing features and the relationship of those features to one another.
Fa et al. propose an approach to 3D design using 3D input devices such as Spaceball(trademark) and Dataglove(trademark) input devices (see, e.g., M. Fa, T. Fernando, and Dew, P. M., xe2x80x9cInteractive Constraint-based Solid Modeling using Allowable Motionxe2x80x9d, Proc. of the 2nd Symposium on Solid Modeling and Applications, 1993, pp.242-252). Although the proposed system is not strictly a VR-CAD environment, the system integrates so-called direct manipulation techniques with a constraint-based assembly design environment. Constraints are automatically recognized based on user interaction with the 3D devices and are used to control the allowable motion of the individual components in a design assembly. A CSG (Constructive Solid Geometry) graph structure is used to store the design, and each component therein is represented by its boundary representation.
The foregoing systems illustrate that current approaches for VR-based CAD have essentially been based on adapting existing CAD user interfaces within VEs. While this approach has the advantage of being straightforward, it (1) does not exploit the complete potential of VEs, and (2) does not adequately address the development of design tools and representations appropriate for the VR environment. A careful analysis of the differences between conventional CAD and VR-CAD systems shows that their requirements are quite different. In large part, this arises from the differences between their user interfaces, and therefore it is helpful to briefly review these interfaces in greater detail.
Most conventional CAD systems are utilize Windows-Icons-Menu-Pointer (WIMP)-based interfaces to an underlying geometric modeler (FIG. 1). In their most typical form, these are text- and mouse-based interfaces, although in some cases 6DOF input devices such as a Spaceballf and dials may also be used. The designer uses these devices to manipulate designs via design editing tools, e.g., by xe2x80x9csketchingxe2x80x9d on 2D planes, creating extrusions, etc. These devices are integrated within the CAD environment via an xe2x80x9cevent drivenxe2x80x9d approach whereby the designer performs a certain action, and the system responds by performing the necessary computations and displaying the results on the graphical monitor. Although it is desirable that the geometric modeler compute the results and display the image as fast as possible, i.e., with minimum delay, the lack of real-time response is not critical in most conventional CAD applications.
However, while the lack of real-time response is not critical in a conventional CAD system, such response is of great importance in a VR-CAD system. Quite simply, if the design does not respond to the user""s inputs almost immediately upon their occurrence, the interface is no longer a xe2x80x9ctruexe2x80x9d VE environment: it does not simulate real-world actions and experiences, and since the motion, voice, etc. no longer have a logical/intuitive link to their outputs, they can be more hindering than helpful. Other differences between CAD and VR-CAD systems center on the multimodality, immersivity, and interactivity of a VE-based application (see, e.g., N. I. Durlach, and A. S. Mavor (Eds), xe2x80x9cPart I: Basic Concepts and Terminology,xe2x80x9d Virtual Reality: Scientific and Technological Challenges, National Academy Press, Washington D.C., 1995). Each of these concepts will now be briefly discussed.
Multimodality involves providing more than one way for the designer to interact with the model, for example, allowing the user to select, grasp and move entities by both keyboard text input and motion input via a motion sensor. Given that such multiple modalities are available to the designer in a VR-CAD system, it is important to provide design-editing tools that optimize these capabilities both individually and collectively (i.e., both taken alone and when interacting) for shape design.
Immersion is the ability of a VE to impart the designer with the feeling of xe2x80x9cpresencexe2x80x9d in the environment being simulated. An implicit assumption is that the better the immersion (the more natural the behavior of the VE), the more productive the designer would be in accomplishing design objectives. Exemplary immersion methods include providing stereoscopic (3D) images and integrating other feedback methods (such as auditory feedback) in the VR-CAD environment.
Interactivity is primarily involved with the aforementioned need for real-time response; as noted, a key difference between CAD and VR-CAD systems is that interactivity assumes great importance in a VR-based system. In the context of a VE, two measures for interactivity are (1) the frame-rate, and (2) the delay. (See, e.g., N. I. Durlach and A. S. Mavor (Eds), xe2x80x9cPart II: Computer Hardware and Software for the Generation of a VE,xe2x80x9d Virtual Reality: Scientific and Technological Challenges, National Academy Press, Washington D.C., 1995). The frame-rate refers to the number of graphical scene updates per second, whereas the delay is the lag perceived by the designer between performing a certain action in the VE and perceiving a response on the graphical display. A minimum rate of 10 frames/second is considered acceptable for a VE application, and a 0.1 second delay is identified as being the maximum allowable in a VE. (See, e.g., P. Zhigeng, Z. Mingmin, Z. Wenting, S. Jiaoying, xe2x80x9cTime-Critical Computing in Virtual Environments,xe2x80x9d Proc. of the 4th International Conference on Computer-Aided Design and Computer Graphics, Oct. 23-25, 1995, Wuhan, China, pp. 712-717.) Both the frame-rate and delay can have significant impact on the interactivity, and hence the effectiveness, of a VE system. The aim in any VE system is to minimize the delay and maximize the frame-rate; however, this requires significant computational resources that remain largely unavailable today.
In large part, difficulties with interactivity arise from the various computations that must be performed in a VR-CAD application, such as intersection detection, rendering, and modeling. Intersection detection is required to detect interference of the user""s hand with a virtual object, or collision between two virtual objects, and is important when performing selection of objects and then manipulation/editing. Additionally, intersection detection is used to provide feedback to the user to indicate that contact has been made with an object, as by visual feedback (highlighting) or auditory feedback.
Rendering involves creation of the display of the VE, including any geometry created by the designer, as well as a graphical representation of the user in the VE (e.g., a display of the designer""s hand). Current research in rendering has focused on achieving acceptable performance by trading off the accuracy of the various software algorithms used (whether they be for intersection detection, rendering, or modeling) for speed. An example of speeding up graphical rendering by reducing the level of detail of images displayed is given in Zhigeng et al. (P. Zhigeng, Z. Mingmin, Z. Wenting, S. Jiaoying, xe2x80x9cTime-Critical Computing in Virtual Environments,xe2x80x9d Proc. of the 4th International Conference on Computer-Aided Design and Computer Graphics, Oct. 23-25, 1995, Wuhan, China, pp. 712-717). Another example is provided by Hubbard, wherein objects in the VE are modeled as spheres for approximate collision detection (P. M. Hubbard, xe2x80x9cApproximating Polyhedra with Spheres for Time-Critical Collision Detection,xe2x80x9d ACM Transactions on Graphics, v. 15, no. 3, Jul. 1996, pp. 179-201). Representing the underlying complex polyhedral geometry of the objects by such spheres enables intersection detection to be completed in a computationally efficient manner.
Modeling relates to the way in which the geometric model is represented and processed within the VR-CAD application. While significant research has been reported on intersection detection and rendering methods for VE applications, modeling has not been researched as extensively. Since the modeling techniques used will have a significant effect on the performance of a VR-CAD system, it will be helpful to briefly review preexisting research on modeling.
Most basic geometric modeling operations in CAD systems utilize a Constructive Solid Geometry (CSG) approach, wherein objects are modeled by primitive geometric elements combined via basic geometric operations such as union, intersection, and negation operations. Since some of these operations are computationally burdensome, some prior researchers have reported attempts to enhance speed by use of specialized or modified operations. As an example, Requicha describes a xe2x80x9crestricted CSGxe2x80x9d approach in which the only allowable operation is a xe2x80x9cgluexe2x80x9d operator that can be applied to solids with disjoint interiors. (See, e.g., A. G. Requicha, xe2x80x9cRepresentation for Rigid Solids: Theory Methods and Systemsxe2x80x9d, Computer Survey, v12, no.4, Dec. 1990, pp 438-464.) Wyvill and Samet describe an octree-based representation (a xe2x80x9cDAG-CSG Treexe2x80x9d) in which objects are modeled in geometric space as a combination (via addition and subtraction) of previously defined primitive objects; in conceptual space, a Directed Acyclic Graph (DAG) is used to represent the solids, with the primitives at the nodes represented by octree data structures. (See, e.g., G. Wyvill, T. L. Kunii, xe2x80x9cA Functional Model for Constructive Solid Geometryxe2x80x9d, The Visual Computer, v. 1, 1985, pp. 3-14.; H. Samet, xe2x80x9cChapter 5: Volume Data, 5.5 Constructive Solid Geometryxe2x80x9d, In The Design and Analysis of Spatial Data Structures, Addison Wesley Publishing Company Inc. 1990.) The DAG results in a tree with nodes that contain a flag indicating whether the primitive was added or subtracted, and matrices describe the relative spatial location and shape of the node. General background information regarding DAGs can be found in, e.g., A. V. Aho, J. E. Hopcroft and J. D. Ullman, Data Structures and Algorithms, Addison Wesley Publishing Company, 1I 1983.
Tree and graph-based structures in conceptual space have been used for assembly modeling wherein the nodes of the graph represent individual parts in the assembly and the arcs of the graph represent affine transformations and other information about the mating parts. The Virtual Link concept proposed by Lee et al. has each arc of an assembly graph store complete information about the type of attachment between the parts (rigid, constrained, etc.), as well as information about the mating surfaces of the parts. (See, e.g., K. Lee, D. C. Gossard, xe2x80x9cA Hierarchical Data Structure for Representing Assemblies: Part 1,xe2x80x9d CAD Journal, v. 17, no. 1, January/February 1985.) The Relationship Graph proposed by Fa et al. (for which a citation was previously given) maintains geometric relationships between parts and assemblies that are represented as CSG (Constructive Solid Geometry) trees. The authors claim that this representation can be used for interactive design by use of 3D hand input devices, but it is unclear as to how the representation will achieve interactive performance suitable for a VE-based system unless a computer system with high processing speed is available.
Other researchers have more specifically addressed modeling methods suitable for VE applications. Virtual Reality Modeling Language (VRML) uses the Scene-Graph representation, which organizes objects into a graph hierarchy in which the leaves of the graphs are the triangular-faceted objects, and the nodes of the graphs are transformations or other such operations. The hierarchy facilitates grouping of objects and allows for optimization of some aspects of collision detection and Scene-Graphs are popular because they provide a representation suitable for real-time displays of predefined static 3D scenes. However, they are not suitable for a VE wherein the geometry may be constantly changing as the user interactively modifies it.
Otherwise, triangular faceted representations of geometric models are typically the representations of choice in VE applications because most current graphics libraries are optimized for them, and they can be accommodated in almost all shape modeling software. However, such a representation has several disadvantages. First, it requires a large amount of memory to store a model, since a model could potentially be composed of millions of triangles. Second, performing editing operations on polygonal models is complex (see, e.g., J. B. Allan, B. Wyvill, I. H. Witten, xe2x80x9cA Methodology for Direct Manipulation of Polygon Meshes,xe2x80x9d New Advances in Computer Graphics: Proceedings of CD International ""89, pp. 451-469). A typical approach to overcome these difficulties is to use a dual representation consisting of both a triangular faceted representation and a complete boundary model. This is the approach taken in the GIVEN (Gesture based Interaction in Virtual Environments) tool-kit (see, e.g., M. Figueiredo, K. Bohm, J. Teixeira, xe2x80x9cAdvanced Interaction Techniques in Virtual Environments,xe2x80x9d Computers and Graphics, v. 17, no. 6, pp. 655-661, 1991) and the ARCADE system (see, e.g., A. Stork, M. Maidhof, xe2x80x9cEfficient and Precise Solid Modeling using a 3D Input Device,xe2x80x9d Proc. of the Fourth Symposium on Solid Modeling and Applications, Atlanta, Ga., May 14-16, 1997, pp. 181-194). These systems maintain interactive performance by having a xe2x80x9ctight couplingxe2x80x9d between the input and output handlers, although it is not clear as to how this is achieved. In addition, the authors point out that complex modeling operations necessitate calls to the ACIS(trademark) solid modeler, with a consequent loss of interactivity.
Another possible approach is to simply use a conventional solid modeler for design representation in the VE just as a conventional CAD system does in the 2D environment). Unfortunately, while a solid modeler application can provide most of the required computational functionality for operations in a VR-CAD system (such as modeling, intersection detection, etc.), it is typically cannot be used in such applications because its slowness makes it unsuitable for the real-time requirements of VE-based systems. This conclusion is borne out by the well known O(n2) of basic solid modeler operations such as creation, editing and interrogation of shapes (where n is the number of topological entities, i.e., vertices, edges or faces in a given solid). Another factor influencing the performance of solid modelers is that they typically store a great deal of information in order to maintain consistency of the model (see, e.g., M. Mantyla, xe2x80x9cAn Introduction to Solid Modeling,xe2x80x9d Computer Science Press), which leads to a further reduction in performance.
As noted earlier, a typical solution to modeling issues in VE-based systems is to use a low-level representation of the model coupled to a more detailed representation of its geometry. As noted earlier, the GIVEN and ARCADE systems use a low-level triangular faceted representation in addition to a high-level complete boundary representation. However, as indicated by the authors of the ARCADE system, not all geometric modeling operations can be handled by the high-level representation and therefore a solid modeler is requiredxe2x80x94but this then results in the possible loss of interactive performance. Therefore, there is still a significant need for methods and apparata which address interactivity problems arising due to modeling issues, as well as the other problems noted above, if efficient and effective CAD systems are to be developed (in particular, effective VR-CAD systems).
The invention, which is defined by the claims set forth at the end of this document, relates to methods and apparata for high-speed computer-aided design of geometric models. As noted earlier, greater design speed (i.e., speed in updating and displaying of the design) generally results in greater interactivity for the user, an advantage which is particularly important if designing is to be performed in computationally burdensome virtual environments (VE). The invention will now be summarized by providing an overview of a preferred embodiment of the invention described in the Detailed Description portion of this document, the preferred embodiment being known as the Virtual Design Software Framework (VDSF).
In VDSF, increased speed is obtained by use of a dual representation of the user-created design, with each representation containing certain information which is useful for modeling the design. These representations may be referred to as the Design Intent Graph (referred to as D) and the Shape Modeling Graph (referred to as S), the term xe2x80x9cgraphxe2x80x9d being used because the representations are best understood when provided in the form of a tree or Directed Acyclic Graph (as will be seen in the Detailed Description section elsewhere in this document). The representations are specially designed to decompose modeling tasks into activities that must be done in real-time and those that can be done asynchronously. Asynchronous performance of modeling tasks may be done in several ways. As a first example, certain modeling data can be pre-computed when features within the design are initially added or edited, and this pre-computed data can reduce the need for calculations later (as will be discussed later, for example, in relation to Geometry Links). As a second example, modeling tasks can be ordered on a spectrum of importance or probability, and those tasks which are more important/likely can be performed first, with less important/likely tasks being performed only if there is sufficient time. This is illustrated later, for example, in the discussion of Proximity Category 1 intersection checks (which are addressed immediately) versus Proximity Category 2 and 3 intersection checks (which are addressed afterwards during processor idle time, if performed at all). Further, in preferred versions of the invention, the representations are constructed so that when action is taken on certain portions of the design, modeling tasks related to that portion are performed locally, rather than over the entire design globally, so as to further decrease computational burden and increase modeling speed. Additionally, the representations are designed to minimize their dependence on conventional solid modeler calculations so that real-time response can be obtained even in computationally-burdensome virtual environments (VE), a result which is not possible if a conventional solid modeler is used.
In the dual representation, the Design Intent Graph D and the Shape Modeling Graph S contain somewhat different information. The focus of D is on storing the xe2x80x9cdesign history,xe2x80x9d the sequence of design steps exercised by the user in creating the design. The focus of S is instead on storage of the features of the design with such detail that the design (and the results of editing the design) can be adequately modeled. However, D and S are xe2x80x9clinkedxe2x80x9d insofar as an update of the design representation in D will generally result in a corresponding update in S.
D stores information such as (1) information about the features/elements the user chose for building the design (their shapes, whether they are solid/positive or void/negative elements, the location of element attachments, orthogonal bounding boxes, etc.); (2) the parent-child hierarchy of the elements within the design (a child element being one which is in immediate attachment with one or more prior parent elements); (3) any user-specified or system-specified design constraints on the elements or their relationships (e.g., two elements are to be spaced apart by some specified distance, etc.). While D does not contain sufficient information to fully support all modeling operations that might be performed on the design, it can support rudimentary operations such as constrained relocation (where relocation of an element also relocates that element""s children, but does not affect the element""s parent); alignment (where an element and its children may be relocated along an axis defined on the element""s parent until a parent edge is reached); and simple boundary box-based intersection checks (where intersections between elements are determined by calculating distances between orthogonal boundary boxes surrounding elements within the design).
S is a more complete representation of the design geometry, and is sufficiently detailed to support almost all modeling operations save for a few which are sufficiently complex that they require the assistance of a solid modeler (for example, intersection determinations between boundary representations). S contains information regarding the elements the user chose to construct the design and the relations between these elements, and is most readily understood when presented as a Directed Acyclic Graph (as in FIG. 28, discussed in greater detail later). In such a graph, the elements are represented by nodes and relation information is primarily represented by links between the nodes. Node/element information includes information such as the shapes of the elements, including the faces, face edges, vertices, and characteristic parameters of the elements; information that can later be used to expedite modeling operations, such as the convex hulls of the elements (which can be used for rapid collision detection between elements, as discussed later); and pointers indicating the links applicable to the face of each component. The S representation in VDSF then uses several types of links, which may be summarized as follows.
The Attachment Link A is used where one element within the design is attached to another element. An attachment link may include information such as an identification of the mating/attachment faces between the elements, and the location of each element with respect to others (i.e., an attachment datum or transformation identifying how the attachment face of one element is positioned with respect to the attachment face on the other element). This information is primarily specified by a type of attachment link known it as a primary attachment link Ap. If an element is a void/negative element rather than a solid/positive element, a secondary attachment link As is used in conjunction with the primary attachment link Ap to indicate negativity. The attachment link A information, when used in conjunction with the node/element information, is sufficient to fully describe most designs and support their editing and rendering. As an example, if a child element is moved with respect to a parent element, the attachment link(s) between them are simply updated to reflect the new location of the child with respect to the parent. Any children of the child element will maintain their locations relative to the child element (unless their attachment links are also modified), and therefore changes in the design are localized about the child element. As another example, if a child element is resized with respect to a parent element, the child""s node information is updated to reflect the new dimensions/configuration of the child, and the attachment link""s location transformation between the child and the parent (and possibly between the child and any children of that child) may also be updated to reflect a change in relative location owing to the child""s resizing. Again, changes in the design will be localized about the child unless other attachment links away from the child are altered. Thus, by representing attachments between elements by the attachment links, and by reflecting attachment changes by updating only the attachment links related to the element being edited, the representation of the design is only updated locally; it will not require a more extensive or xe2x80x9cglobalxe2x80x9d recalculation. This results in a significant decrease in computation time, allowing the design to be updated and rendered very rapidly so that greater interactivity can be attained.
Further links may then be used if even greater gains in interactivity are desired. The Proximity Link P can be used to expedite intersection (element collision) detection during editing activities by precomputing certain quantities useful in intersection detection, thereby reducing later computation time when intersection detection is required. The P links enable rapid intersection detection by storing all distances d between the convex hull of an element in question and the convex hulls of all other elements which are neither parents nor children of that element. These other non-parent/non-child elements are then ranked in order of increasing distance d (i.e., in order of proximity). When the element in question is later edited (e.g., moved), a convex hull intersection check is only performed between the element and some predetermined number of the most proximal non-parent/non-child elements, and the intersection checks are performed in order of rank. If a convex hull intersection is detected between elements, a xe2x80x9cfullxe2x80x9d intersection check between the boundary representations of the elements can be performed with a call to a solid modeler. Thus, the time-consuming intersection check by the solid modeler is only performed in certain instances when prior testsxe2x80x94whose parameters are largely pre-computed in prior time stepsxe2x80x94indicate that an intersection is likely. Additional time advantages are realized if the non-parent/non-child elements are further ranked into three categories:
Proximity Category 1: Elements which have the same parent as the element in question and which are attached to the same parent face as the element in question:
Proximity Category 2: Elements which have the same parent as the element in question but which are not attached to the same parent face as the element in question; and:
Proximity Category 3: Elements which do not have the same parent as the element in question.
In general, this categorization further classifies elements in order of their probability of intersection to the element in question, with intersections being most likely for Category 1 elements and least likely for Category 3 elements. By performing the aforementioned intersection detection test on elements within Category 1 first, and then proceeding to succeeding categories if no intersections are detected, further time savings are obtained because intersections are sought where they are most likely to occur.
If an intersection is detected, the designer can be asked to confirm or deny whether the intersection was intended before being allowed to make further design changes. In VDSF, many proximity links are categorized as xe2x80x9csoftxe2x80x9d because they allow the designer to permit intersection if he/she wishes to do so. It is also possible to provide xe2x80x9chardxe2x80x9d proximity links which do not allow intersections, or which do not permit the elements subject to the proximity link to violate some predetermined proximity condition. As examples, hard proximity links can restrict elements to remain at some predefined distance, or require them to remain above or below some predefined distance. Such hard proximity links can be enforced by checking methods similar to, the aforementioned method of intersection checks, e.g., the distances d can be checked for compliance with predefined distance constraints.
Geometry links G may also be provided to attain further benefits in computational speed. Geometry links are used to store precalculated information regarding the features of elements, or regarding relationships between elements, so that this information is readily available for later use in editing operations. As one example, xe2x80x9cparallel facexe2x80x9d geometry links may exist between opposite parallel faces within an element so that certain later design activities requiring an opposite parallel face determination (e.g., the piercing of the element by a through-hole) are expedited. Similarly, xe2x80x9copposite facexe2x80x9d geometry links may be formed between spaced parallel faces on different elements so that later design activities requiring an opposite parallel face determination (e.g., addition of a xe2x80x9cbridgexe2x80x9d element) are expedited.
Thus, it is seen that the foregoing design representation can allow several important benefits: (1) it can allow localization of the effect of editing operations (i.e., editing can occur on localized design elements rather than on the design globally); (2) proximity of design elements in the xe2x80x9cconceptual spacexe2x80x9d of the representation can be translated to physical proximity of elements in geometric space to enable faster intersection determination between design elements; and (3) the geometry of design elements can be precomputed so as to avoid potentially expensive computations during editing. These benefits each provide significant computational time savings, which translates to higher interactivity in the design system.